1. Field of the Invention
This invention relates to a viterbi decoder used for maximum likelihood decoding of the convolutional code.
2. Description of the Related Art
A viterbi decoder is used in a maximum likelihood decoding method for decoding the convolutional code. Among plural known code sequences, a path closest in the code distance to an input code sequence is selected as being the maximum likelihood path and decoded data is obtained in association with the selected path. Viterbi decoding has a high correction capability against random errors occurring in a call path and gives a particularly high encoding gain in combination with a soft decision demodulation system. For example, in a satellite communication system on which strict limitations are imposed on the electric power in view of adverse effects by interference waves, the convolutional code is used as an error correction code, and a viterbi decoder is used for decoding.
The viterbi decoding algorithm is briefly explained.
consider the convolutional code with the generating polynominals for which are given by EQU G.sub.0 (D)=1+D.sup.2 EQU G.sub.1 (D)=1+D+D.sup.2
with the code rate R=1/2 and the constraint length K=3. FIG. 1 shows an illustrative structure generating such code. In this figure, input data is sequentially delayed by delay elements 301, 302, such as two flip-flops 301, 302. The input data is summed by an adder 303 to data from the delay element 302 so as to be taken out as an output G.sub.0. Moreover, the input data is summed by adders 304, 305 to data from the delay elements 301, 302 so as to be taken out as an output G.sub.1.
If the outputs of the delay elements 301, 302 in the encoder are b.sub.1, b.sub.2, respectively, four states (00), (01), (10) and (11) are possible as the encoder states (b.sub.1 b.sub.2). There are two possible transition states at all times for a given input.
That is, if, for an input 0, the current state is (00) or (10), the state transfers to (00). If the current state is (01) or (11), the state transfers to (10). If, for an input 1, the current state is (00) or (10), the state transfers to (01). If the current state is (01) or (11), the state transfers to (11).
Such state transition is shown as a trellis diagram in FIG. 2, in which a solid-line branch indicates transition for an 0 input, while a broken-line branch indicates transition for an input 1. The numerals entered along the branches denote the code (G.sub.0 G.sub.1) of FIG. 1 outputted on occurrence of the branch transition.
As apparent from FIG. 2, two paths become confluent at the time of transition to respective states. Of the two paths to the respective states in the viterbi decoding algorithm the maximum likelihood path (most probable path) is selected, and the path which has survived is selected up to a pre-set length. The most probable ones of the paths selected in the respective states are detected for decoding the reception code.
The viterbi decoder, which decodes the convolutional code based on the above-described viterbi algorithm, is basically made up of a branch metric computing unit for computing the metric between the reception data sequence (reception sequence) and the respective branches, an ACS (adder, comparator, selector) computing means for selecting the surviving path and for computing the path metric of the surviving path, a path metric storage unit for storing the values of the path metrics in the respective states, a path memory for storing the output of the selected path and a maximum likelihood decision unit for detecting the address of the most probable path metric for controlling the path memory.
In the ACS computing unit, the surviving path in each state is selected in accordance with a so-called path metric transition diagram, and the path metric of the surviving path is computed. This path metric transition diagram is formulated on the basis of the trellis diagram shown in FIG. 2
If the code shown by the trellis diagram of FIG. 2 is used, the path metric transition diagram is as shown in FIGS. 3A and 3B. That is, in the trellis diagram shown in FIG. 2, two paths, namely a path in which a code (00) is outputted from the state (00), and a path in which a code (11) is produced from the state (10), become confluent in the state (00). Therefore, the path metric S00(new) of the current state (00) is EQU S00(new)a=S00(old)+BM00
or EQU S00(new)b=S10(old)+BM11
if the value of the state of the previous time point (path metric) is denoted as S00(old), S10(old) and the branch metric is denoted by BM00and BM11. That is, a path with a smaller one of the two path metrics S00(new)a and S00(new)b being currently calculated is selected and the value of the selected path (path metric) is outputted as the path metric S00(new) of the current state (00). The path selection information at this time is outputted simultaneously.
On the other hand, a path producing a code (11) from the state (00) and a path producing a code (00) from the state (10), totaling two paths, are confluent at the state (01). Therefore, the current path metric S01 (new) is EQU S01(new)a=S00(old)+BM11
or EQU S01(new)b=S10(old)+BM00
Also, a path producing a code (01) from the state (01) and a path producing a code (10) from the state (11), totaling two paths, are confluent at the state (10). Therefore, the current path metric S10(new) is EQU S10(new)a=S01(old)+BM01
or EQU S10(new)b=S11(old)+BM10
In addition, a path producing a code (10) from the state (01) and a path producing a code (01) from the state (11), totaling two paths, are confluent at the state (11). Therefore, the current path metric S11(new) i s EQU S11(new)a=S01(old)+BM10
or EQU S11(new)b=S11(old)+BM01
On the basis of the foregoing, a path metric transition diagram shown in FIGS. 3A and 3B is prepared.
In a conventional viterbi decoder, it is known to perform ACS calculations by time divisional processing and to use a random access memory (RAM) as a path selection information memory designed to store the path selection information obtained from the result of ACS calculations. In such viterbi decoder, the path selection information obtained by the ACS processing is simply written in the RAM each time the information corresponding to the number of bits per each address of the RAM is available. After all ACS processing comes to a close and the path selection information is written in the RAM, the past path selection information is sequentially read out for a maximum likelihood decision and the decoding result is estimated and prepared.
In this case, since the past path selection information is read out after writing all of the path selection information into the RAM as a result of the ACS computing by time divisional processing, the processing time for writing is separate from that for readout, with the result that the processing time becomes longer than in the path selection information storage circuit employing flip-flops or the like, and hence the high-speed viterbi decoding cannot be realized. Moreover, in the case of the path selection information storage circuit employing flip-flops, since the contents of all states are accessed when reading out the path selection information for making a maximum likelihood decision, low power consumption cannot be achieved easily.